package com.kobe.algorithm.niue;

import java.util.*;

/**
 * @author ：caopengfei
 * @date ：2021/2/25
 */
public class LRUSolution {

    class Node{
        Node perNode;
        Node afterNode;
        int value;
        int key;

        public Node(int value, int key) {
            this.value = value;
            this.key = key;
        }
    }


    //HashMap 进行的数据缓存
    Map<Integer,Node> cache = new HashMap<>();
    //缓存大小
    int capacity;
    //当前大小
    int size;
    //链表头部
    private Node head = new Node(-1,-1);
    //链表尾部
    private Node lastNode =  new Node(-1,-1);

    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU(int[][] operators, int k) {
        head =
        lastNode = new Node(0,0);
        head.afterNode = lastNode;
        lastNode.perNode = head;
        capacity = forMatterCapacity(k);
        List<Integer> listArr= new ArrayList<>();
        for(int i = 0; i < operators.length;i++){
            int [] op = operators[i];
            if(op.length == 3 && op[0] == 1 ){
                put(op[1],op[2]);
            }else if(op.length == 2 && op[0] == 2 ){
                int  value = get(op[1]);
                listArr.add(value);
            }
        }
        int[] list = new int[listArr.size()];
        for (int i = 0; i < listArr.size(); i++) {
            list[i] = listArr.get(i);
        }
        return list;
    }

    private int forMatterCapacity(int k){
        if(k < 1 || k> Math.pow(10,5)){
            return (int)Math.pow(10,5);
        }else{
            return k;
        }
    }

    private boolean checkKeyAndValue(int key,int value){
        int max = (int)(2*Math.pow(10,9) );
        int min = (int)(-2*Math.pow(10,9));
        return value< min || value> max || key< min || key> max;
    }


    /**
     * 查询一个元素
     */
    public int get(int key){

        if(!cache.containsKey(key)) {
            return -1;
        }else{
            Node node = cache.get(key);
            moveToHead(node);
            return node.value;
        }
    }

    /**
     * 加入一个元素
     */
    public void put(int key,int value){
        if(!checkKeyAndValue(key,value)){
            return;
        }
        Node node = cache.get(key);
        if(node == null){
            Node newNode = new Node(key,value);
            cache.put(key,newNode);
            appendToHead(newNode);
            ++size;
            if(size > capacity){
                Node lastNode = removeLastNode();
                cache.remove(lastNode.key);
                --size;
            }
        }else{
            node.value = value;
            moveToHead(node);
        }
    }
    /**
     * 将元素添加到链表头部
     */
    private void appendToHead(Node node ){
          head.afterNode.perNode = node;
          node.afterNode = head.afterNode;
          head.afterNode = node;
          node.perNode = head;
    }

    /**
     * 移除一个元素
     */
    public void removeNode(Node node){
        node.perNode.afterNode = node.afterNode;
        node.afterNode.perNode = node.perNode;
    }
    /**
     * 删除链表末尾的元素
     */
    private Node removeLastNode(){
        Node node = lastNode.perNode;
        removeNode(node);
        return node;
    }
    /**
     * 将元素移动到链表头部
    */
    private void moveToHead(Node node){
        removeNode(node);
        appendToHead(node);
    }

    public static void main(String[] args) {

        int[][] test =  {{1,1,1},{1,2,2},{1,3,2},{2,1},{1,4,4},{2,2}};

        LRUSolution solution = new LRUSolution();
        long start = System.currentTimeMillis();
        System.out.println(Arrays.toString(solution.LRU(test,3)));
        System.out.println(System.currentTimeMillis() - start);
    }

}
